#include "stdio.h"
#include "stdlib.h"

#define maxsize 20
//定义优先级
const char ADD_SUB = '+';
const char MUL_DIV = '-';

typedef struct Operation
{
    char s[maxsize];
    int top;
};

void match(Operation &stack1, Operation &stack2)
{
    while (stack1.s[stack1.top - 1] != ')')
    {
        stack1.top--;
        stack2.s[stack2.top++] = stack1.s[stack1.top];
    }
    stack1.top--; //把 '('去除
}

void post_tranform(char *op)
{
    Operation s1, s2;
    s1.top = s2.top = 0; //s1存放操作数 s2临时存放运算符
    int i = 0;
    while (*(op + i) != '\0')
    {
        switch (*(op + i))
        {
        case '(':
            s2.s[s2.top++] = *(op + i++);
            break;
        case ')':
            //执行弹出操作
            match(s2, s1);
            i++;
            break;
        case '+':
        case '-':
            //与栈顶元素优先级相比较 空栈 或者 ( 就入栈 否则弹出s2栈顶到s1 再次进行比较
            //ADDITION 和 SUBSTRACT 都为'1'
            if (s2.top = 0 || s2.s[s2.top - 1] == '(')
            {
                s2.s[s2.top++] = ADD_SUB;
            }
            else
            {
                while (s2.s[s2.top - 1] == ADD_SUB || s2.s[s2.top - 1] == MUL_DIV)
                    s1.s[s1.top++] = s2.s[s2.top--];
                s2.s[s2.top++] = ADD_SUB;
            }
            i++;
            break;
        case '*':
        case '/':
            if (s2.top = 0 || s2.s[s2.top - 1] == '(')
            {
                s2.s[s2.top++] = ADD_SUB;
            }
            else
            {
                while (s2.s[s2.top - 1] == MUL_DIV)
                    s1.s[s1.top++] = s2.s[s2.top--];
                s2.s[s2.top++] = MUL_DIV;
            }
            i++;
            break;
        //数字就直接进s1
        default:
            s1.s[s1.top++] = *(op + i++);
            break;
        }
    }
    //依次把s2里面的数据弹出 存在s1里面
    while (s2.top > 0)
    {
        s2.top--;
        s1.s[s1.top++] = s2.s[s2.top];
    }
    for (int k = 0; k < s1.top; k++)
    {
        printf("%2c", s1.s[k]);
    }
}

int main()
{
    char *op = "1+((2+3)×4)-5";
    post_tranform(op);
    return 0;
}